package offer.offer02;

import java.util.Arrays;
import java.util.Stack;

/**
 * 对于搜索树, 分治算法确实很管用, 自带了左右子树的明显区分
 * 注意, 这是二叉搜索树! 只是判断是不是二叉搜索树的条件, 二叉搜索树没必要是完全二叉树,
 * 同时, 没有办法通过数组还原这个二叉树
 * 因为后序遍历是先递归左子树在递归右子树的, 所以对于一个查找树的后序遍历结果,
 * 肯定是有很明显的[左子树, 右子树, 根]这么个分块的,
 */
public class Solution33 {
    public boolean verifyPostorder(int[] postorder) {
        //空树为二叉查找树
        if(postorder == null || postorder.length == 0) return true;
        int postLen = postorder.length;
        int rootNum = postorder[postLen - 1];
        for(int searchNum = 0; searchNum < postLen - 1; searchNum ++){
            if(postorder[searchNum] > rootNum){
                for(int j = searchNum + 1; j < postLen - 1; j++){
                    if(postorder[j] < rootNum) return false;
                }// 另外一半是不是也要判断是不是都>rootNum?
                return verifyPostorder(Arrays.copyOfRange(postorder, 0, searchNum)) &&
                        verifyPostorder(Arrays.copyOfRange(postorder, searchNum, postLen - 1));
            }
        }
        return verifyPostorder(Arrays.copyOfRange(postorder, 0, postLen - 1));
    }

    // 一样。
    public boolean verifyPostorder2(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }

    // todo: 重要, 但看不懂。
    // 二叉搜索树的各种遍历, 有着独特的性质。
    public boolean verifyPostorder3(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int parent = Integer.MAX_VALUE;
        //注意for循环是倒叙遍历的
        for (int i = postorder.length - 1; i >= 0; i--) {
            int cur = postorder[i];
            //当如果前节点小于栈顶元素，说明栈顶元素和当前值构成了倒序,
            //说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
            while (!stack.isEmpty() && stack.peek() > cur)
                parent = stack.pop();
            //只要遇到了某一个左子节点，才会执行上面的代码，才会更
            //新parent的值，否则parent就是一个非常大的值，也就
            //是说如果一直没有遇到左子节点，那么右子节点可以非常大
            if (cur > parent)
                return false;
            //入栈
            stack.add(cur);
        }
        return true;
    }

    public static void main(String[] args) {
        int[] input = new int[]{4, 8, 6, 12, 16, 14, 10};
        System.out.println(new Solution33().verifyPostorder3(input));
    }
}
